1. Field of the Invention
The present invention relates to the field of data transfers between nodes in a parallel processing system, and more particularly, to a method and apparatus for integrated local and express routing in a multiprocessor.
2. Art Background
In recent years, parallel processing computer architectures have demonstrated substantial performance advantages over more traditional sequential computer architectures. In particular, as computational needs have grown, and the performance advantages offered by parallel processing have come to be recognized, highly parallel computer architectures have generated considerable interest. One such parallel computer architecture comprises a two-dimensional mesh of processor nodes, each of these nodes having an independent processor with computing power.
FIG. 1 illustrates a two dimensional mesh of nodes 102, each node being coupled to a router 104. The processing nodes together form a large parallel processing system. The routers 104 are used to transfer messages between the processor nodes 102.
The four directions in which a message can travel within the mesh architecture are designated as North, East, West and South. Accordingly, as shown in FIG. 1, each message routing chip includes eight separate routing ports, a pair of North input and output routing ports, a pair of East input and output routing ports, a pair of West input and output routing ports, and a pair of South input and output routing ports. When orienting a message routing chip within the mesh topology, the East direction is chosen to correspond to the positive x direction, the West direction is chosen to correspond to the negative x direction, the North direction is chosen to correspond to the positive y direction, and the South direction is chosen to correspond to the negative y direction. Each message routing chip 104 also has a processor port comprising a uni-directional input port for receiving data from processor node 102 and a uni-directional output port for delivering data to the processor node.
When data is to be sent from a first processor node to a second processor node, the message routing chip coupled to the first processor node initially receives the data through its input processor port. The data then travels through the mesh until it reaches the appropriate message routing chip coupled to the second processor node. The data is delivered to the second processor node via that message routing chip's output processor port. In a two dimensional mesh, data typically is first routed only in the x direction, and then in the y direction. When a message is received by a message routing chip, a header in the message contains a word indicating the displacement (in nodes) in the x dimension that the message must travel in the mesh to reach the x coordinate of the destination node. A sign bit in the header also indicates the direction of travel in the x dimension. Similarly, another word in the header of the message indicates the displacement (in nodes) in the y dimension that the message must travel to reach the y coordinate of the destination node, and includes a sign bit indicating the direction of travel, either North or South.
As a message passes through each router in the x dimension, the displacement is decremented. When a router receives a message with the x displacement equal to zero, the message is no longer routed in the x dimension. Rather, the same process starts over again in the y dimension. As the message passes through each router in the y dimension, the y displacement is decremented. When a router receives a message with both the x and y displacements equal to zero, the message is delivered to the router output port to the processor node associated with that final router.
A further description of router technology may be found in U.S. patent application Ser. No. 892,535, filed on Jun. 1, 1992, and assigned to the assignee of the present invention, and in C.M. Flaig, VLSI Mesh Routing Systems, Master's Degree thesis, 5241:TR:87, California Institute of Technology, May, 1987.
One of the goals of any message routing system is to increase the message transmission bandwidth. One measurement of bandwidth is the bi-sectional bandwidth in bytes per second. The bi-sectional bandwidth is measured by creating an imaginary cut between any two routers and measuring how much information flows in one direction across the cut.
There are two obvious ways to increase the bi-sectional bandwidth. First, the frequency of the system may be increased. However, the technology to do so is currently prohibitively expensive and results in increased power consumption. Further, technological barriers, such as inherent semiconductor delays, limit the possible maximum frequency.
Another way to increase bandwidth would be to increase the bus width. However, note that every router has ten uni-directional buses--four pairs of North, East, West and South buses and one pair of buses for communicating with the processor node. Thus, for every bit added to increase the bus width, ten bits are added to the routing chip used in a two dimensional mesh. Routing chips with 16 bit bus widths already have approximately 300 pins and are on the order of two inches square. The addition of substantially more pins would create an unacceptable package size that would occupy too much real estate on the circuit boards into which the routers are plugged.
A more feasible way to increase bi-sectional bandwidth is to periodically place additional "express" routers in the mesh that are dedicated only to transferring messages over long hops between the local routers already present in the mesh. Referring to FIGS. 2 and 3, the two dimensional mesh comprises a network of local routers 202. An express router 204 is interposed into the network after every fourth local router in both the x and y dimensions.
The operation of the express router 204 is described in more detail with respect to FIGS. 3 and 4. FIG. 3 illustrates a row of the two dimensional mesh of FIG. 2, including express routers 204 used to route messages in the x dimension.
FIG. 4 illustrates the structure of an express router 204. In the positive x direction, messages are input to the XP.sup.+ IN or LOC.sup.+ IN ports depending on whether the message was sent by an express router or a local router, respectively. Messages are output on ports XP.sup.+ OUT or LOC.sup.+ OUT to an adjacent express or local router, respectively, depending on the conditions described below. The express router operates in the negative x direction in an analogous manner using the XP.sup.- IN, LOC.sup.- IN, XP.sup.- OUT and LOC.sup.- OUT ports.
In the example of FIG. 3, each express router for a particular dimension is separated by four local routers. In this case, the network is said to have a "skip size" of four routers. When the express router 204 receives a message from an adjacent local router or from another express router, it determines whether the displacement in the dimension handled by the router is greater than or equal to the skip size. If so, the express router transmits the message to the next express router in that dimension through ports XP.sup.+ OUT or XP.sup.- OUT over an express bus coupling the two express routers, and the displacement in that dimension is decremented by the skip size. If the displacement is less than the skip size, then the express router 204 transmits the message through ports LOC.sup.- OUT or LOC.sup.+ OUT to the next adjacent local router 202 over a local bus. This process continues until the message reaches its final destination and the displacements in all dimensions have been decremented to zero.
The advantages and disadvantages of using express routers will now be discussed. The express routers of FIGS. 2 and 3 provide two paths past any point in the mesh, thus doubling the bi-sectional bandwidth. In one dimension, this increase in performance is obtained by adding only 25% more routers for a skip size of four. In two dimensions, 50% more routers are added to double the bandwidth for the same skip size. Relatively speaking, the increase in the number of components is not bad considering the gain in bandwidth. However, as mentioned above, each express router occupies approximately two inches square of board space, while board space is at a premium. Further, for short hops the addition of the express routers increases message latency, the time it takes for a message to travel from one node to another. Referring to FIG. 3, one can see that in the simplest case of a short hop between the two nodes connected to the local routers 202 that straddle an express router 204, the message latency is increased from two routers to three routers.
It is desirable to obtain an increase in bi-sectional bandwidth while at the same time minimizing the number of extra components required in the mesh. In addition, it is desirable to reduce latency and, because of circuit packaging constraints, to keep the pin count to a minimum.